package com.awei.study.dataStructure.link;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//反向单项列表
public class Tran_linkList {
    static class LinkNode {
        int value;
        LinkNode next;
        public LinkNode(int value,LinkNode next) {
            this.value = value;
            this.next=next;
        }
    }


    /**
     * 使用创建新链表反转
     */

    @Test
    public void test1() {
        LinkNode l1 = prepareData();
        print(l1);
        LinkNode head = null;
        while (l1 != null) {
            LinkNode first = new LinkNode(l1.value,head);
            head = first;
            l1 = l1.next;
        }
        print(head);
    }

    /**
     * 使用原有列表进行反转
     */
    @Test
    public void test2() {
        LinkNode l1 = prepareData();
        print(l1);
        list list1 = new list(l1);
        list list2 = new list(null);
        while(true) {
            LinkNode first = list1.removeFirst();
            if(first == null) {
                break;
            }
            list2.addFirst(first);
        }
        print(list2.head);
    }

    /**
     * 递归进行反转
     */
    @Test
    public void test3() {
        LinkNode l1 = prepareData();
        print(l1);
        LinkNode head = bfsLinkNode(l1);
        print(head);
    }


    /**
     * 三个链表 循环转换 new1 old1 old2
     *
     * o1/n1    o2
     * 1        2       3       4       5
     *
     * o2       o1/n1
     * 2        1       3       4       5
     *
     * n1       o1      o2
     * 2        1       3       4       5
     *
     * o2       n1       o1
     * 3        2        1      4       5
     *
     * n1                o1     o2
     * 3        2        1      4       5
     */
    @Test
    public void test4() {
        LinkNode l1 = prepareData();
        print(l1);
        if(l1 == null || l1.next == null) print(l1);
        LinkNode o1 = l1;
        LinkNode n1 = l1;
        LinkNode o2 = o1.next;
        while(o2 != null) {
//            print(o2);
            o1.next = o2.next;
            o2.next = n1;
            n1 = o2;
            o2 = o1.next;
        }
        print(n1);
    }


    /**
     * n1
     * null
     * n1       o1      o2
     * null,    1       2       3       4       5
     * o1       n1      02
     * 1        null,   2       3       4       5
     * n1               o1      o2
     * 1        null,   2       3       4       5
     * o1        n1             o2
     * 2        1       null,   3       4       5
     */
    @Test
    public void test5() {
        LinkNode l1 = prepareData();
        print(l1);
        if(l1 == null || l1.next == null) print(l1);
        LinkNode o1 = l1;
        LinkNode n1 = null;
        while(o1 != null) {
            LinkNode o2 = o1.next;
            print(o1);
            o1.next = n1;
            n1 = o1;
            o1 = o2;
        }
        print(n1);
    }

    public LinkNode bfsLinkNode(LinkNode p) {
        if(p == null || p.next == null) return p;
        LinkNode linkNode = bfsLinkNode(p.next);
        p.next.next = p;
        p.next = null;
        return linkNode;
    }


    static class list {
        LinkNode head;

        public list(LinkNode head) {
            this.head = head;
        }

        public void addFirst(LinkNode first) {
            first.next = head;
            head = first;
        }

        public LinkNode removeFirst() {
            LinkNode first = head;
            if(head != null) {
                head = head.next;
            }
            return first;
        }
    }

    // 输出链表
    public static void print(LinkNode head) {
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.value);
            head = head.next;
        }
        System.out.println(Arrays.toString(list.toArray()));
    }
    // 准备数据
    public static LinkNode prepareData() {
        LinkNode l5 = new LinkNode(5,null);
        LinkNode l4 = new LinkNode(4,l5);
        LinkNode l3 = new LinkNode(3,l4);
        LinkNode l2 = new LinkNode(2,l3);
        LinkNode l1 = new LinkNode(1,l2);
        return l1;
    }



}
